An Optimal and Progressive Approach to Online Search of Top-k Influential Communities

摘要

Community search over large graphs is a fundamental problem in graphanalysis. Recent studies propose to compute top-k influential communities,where each reported community not only is a cohesive subgraph but also has ahigh influence value. The existing approaches to the problem of top-kinfluential community search can be categorized as index-based algorithms andonline search algorithms without indexes. The index-based algorithms, althoughbeing very efficient in conducting community searches, need to pre-compute aspecial-purpose index and only work for one built-in vertex weight vector. Inthis paper, we investigate on-line search approaches and propose aninstance-optimal algorithm LocalSearch whose time complexity is linearlyproportional to the size of the smallest subgraph that a correct algorithmneeds to access without indexes. In addition, we also propose techniques tomake LocalSearch progressively compute and report the communities in decreasinginfluence value order such that k does not need to be specified. Moreover, weextend our framework to the general case of top-k influential community searchregarding other cohesiveness measures. Extensive empirical studies on realgraphs demonstrate that our algorithms outperform the existing online searchalgorithms by several orders of magnitude.